{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Bus Routes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #breadth-first-search #array #hash-table"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #广度优先搜索 #数组 #哈希表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numBusesToDestination"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #公交路线"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个数组 <code>routes</code> ，表示一系列公交线路，其中每个 <code>routes[i]</code> 表示一条公交线路，第 <code>i</code> 辆公交车将会在上面循环行驶。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，路线 <code>routes[0] = [1, 5, 7]</code> 表示第 <code>0</code> 辆公交车会一直按序列 <code>1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ...</code> 这样的车站路线行驶。</li>\n",
    "</ul>\n",
    "\n",
    "<p>现在从 <code>source</code> 车站出发（初始时不在公交车上），要前往 <code>target</code> 车站。 期间仅可乘坐公交车。</p>\n",
    "\n",
    "<p>求出 <strong>最少乘坐的公交车数量</strong> 。如果不可能到达终点车站，返回 <code>-1</code> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>routes = [[1,2,7],[3,6,7]], source = 1, target = 6\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>最优策略是先乘坐第一辆公交车到达车站 7 , 然后换乘第二辆公交车到车站 6 。 \n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12\n",
    "<strong>输出：</strong>-1\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= routes.length <= 500</code>.</li>\n",
    "\t<li><code>1 <= routes[i].length <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>routes[i]</code> 中的所有值 <strong>互不相同</strong></li>\n",
    "\t<li><code>sum(routes[i].length) <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 <= routes[i][j] < 10<sup>6</sup></code></li>\n",
    "\t<li><code>0 <= source, target < 10<sup>6</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [bus-routes](https://leetcode.cn/problems/bus-routes/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [bus-routes](https://leetcode.cn/problems/bus-routes/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,2,7],[3,6,7]]\\n1\\n6', '[[7,12],[4,5,15],[6],[15,19],[9,12,13]]\\n15\\n12']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:\n",
    "        if source == target:\n",
    "            return 0\n",
    "        bus_station = defaultdict(set)\n",
    "        for station, buses in enumerate(routes):\n",
    "            for bus in buses:\n",
    "                bus_station[bus].add(station)\n",
    "        \n",
    "\n",
    "        visited_stops = set()  # 已经访问过的站点\n",
    "        visited_buses = set()  # 已经乘坐过的公交车\n",
    "        queue = deque([(source, 0)])  # 队列中存储（当前站点，乘坐公交车的数量）\n",
    "\n",
    "        # BFS搜索\n",
    "        while queue:\n",
    "            stop, bus_count = queue.popleft()\n",
    "            if stop == target:\n",
    "                return bus_count\n",
    "            for bus in bus_station[stop]:\n",
    "                if bus not in visited_buses:\n",
    "                    visited_buses.add(bus)\n",
    "                    for next_stop in routes[bus]:\n",
    "                        if next_stop not in visited_stops:\n",
    "                            visited_stops.add(next_stop)\n",
    "                            queue.append((next_stop, bus_count + 1))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sys\n",
    "import copy\n",
    "class Solution(object):\n",
    "    def numBusesToDestination(self, routes, S, T):\n",
    "        if S is None or T is None:\n",
    "            return -1\n",
    "        if S == T:\n",
    "            return 0\n",
    "        li_s = []\n",
    "        li_t = []\n",
    "        count_s = count_t = 0\n",
    "        visit_s = [0]*len(routes)\n",
    "        visit_t = [0]*len(routes)\n",
    "        for id, route in enumerate(routes):\n",
    "            if route.count(S) != 0:\n",
    "                count_s += 1\n",
    "                visit_s[id] = 1\n",
    "                li_s.append(route)\n",
    "            if route.count(T) != 0:\n",
    "                count_t += 1\n",
    "                visit_t[id] = 1\n",
    "                li_t.append(route)\n",
    "        if not li_s or not li_t:\n",
    "            return -1\n",
    "        cur_s = 1\n",
    "        cur_t = 1\n",
    "\n",
    "        for route in li_s:\n",
    "            if route in li_t:\n",
    "                return cur_s + cur_t - 1\n",
    "        while li_s or li_t:\n",
    "            if li_s:\n",
    "                c = 0\n",
    "                while count_s > 0:\n",
    "                    rt = li_s.pop(0)\n",
    "                    for id, route in enumerate(routes):\n",
    "                        if visit_s[id] == 0 and set(route) & set(rt):\n",
    "                            c += 1\n",
    "                            visit_s[id] = 1\n",
    "                            li_s.append(route)\n",
    "                    count_s -= 1\n",
    "                count_s = c\n",
    "                cur_s += 1\n",
    "            for route in li_s:\n",
    "                if route in li_t:\n",
    "                    return cur_s + cur_t - 1\n",
    "            if li_t:\n",
    "                c = 0\n",
    "                while count_t > 0:\n",
    "                    rt = li_t.pop(0)\n",
    "                    for id, route in enumerate(routes):\n",
    "                        if visit_t[id] == 0 and set(route) & set(rt):\n",
    "                            c += 1\n",
    "                            visit_t[id] = 1\n",
    "                            li_t.append(route)\n",
    "                    count_t -= 1\n",
    "                count_t = c\n",
    "                cur_t += 1\n",
    "            for route in li_s:\n",
    "                if route in li_t:\n",
    "                    return cur_s + cur_t - 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def numBusesToDestination(self, routes, S, T):\n",
    "        \"\"\"\n",
    "        :type routes: List[List[int]]\n",
    "        :type S: int\n",
    "        :type T: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # 无向无权图最短路径问题\n",
    "        # 这里的vertex是集合\n",
    "        # 若两个vertex之间有交集，则认为二者之间有边\n",
    "        if S == T:\n",
    "            return 0\n",
    "        hashmap = {}\n",
    "        start = []\n",
    "        N = len(routes)\n",
    "        for i in range(N):\n",
    "            hashmap[i] = set(routes[i])\n",
    "            if S in hashmap[i]:\n",
    "                if T in hashmap[i]:\n",
    "                    return 1\n",
    "                start.append(i)\n",
    "        graph = defaultdict(list)\n",
    "        for i in range(N):\n",
    "            for j in range(i+1, N):\n",
    "                if hashmap[i] & hashmap[j]:\n",
    "                    graph[i].append(j)\n",
    "                    graph[j].append(i)\n",
    "        queue = deque(start)\n",
    "        visited = set(start)\n",
    "        ans = 1\n",
    "        while queue:\n",
    "            length = len(queue)\n",
    "            for _ in range(length):\n",
    "                cur = queue.popleft()\n",
    "                for adj in graph[cur]:\n",
    "                    if T in hashmap[adj]:\n",
    "                        return ans+1\n",
    "                    if adj not in visited:\n",
    "                        visited.add(adj)\n",
    "                        queue.append(adj)\n",
    "            ans += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n",
    "        bus = []\n",
    "        if S == T:\n",
    "            return 0\n",
    "        for i in routes:\n",
    "            bus.append(tuple(i))\n",
    "        beginset = set()\n",
    "        for i in bus:\n",
    "            if S in i:\n",
    "                beginset.add(i)\n",
    "        res = 0\n",
    "        while(beginset):\n",
    "            res += 1\n",
    "            for i in beginset:\n",
    "                if i in bus:\n",
    "                    bus.remove(i)\n",
    "            tmp = set()\n",
    "            tmp_beginset = set()\n",
    "            for i in beginset:\n",
    "                for j in i:\n",
    "                    tmp.add(j)\n",
    "            if T in tmp:\n",
    "                return res\n",
    "            for i in bus:\n",
    "                for j in i:\n",
    "                    if j in tmp:\n",
    "                        tmp_beginset.add(i)\n",
    "                        break\n",
    "            beginset = tmp_beginset\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n",
    "        if S == T:\n",
    "            return 0\n",
    "        a = [set(i) for i in routes]\n",
    "        s = {S}\n",
    "        ans = 0\n",
    "        while a and s:\n",
    "            b = []\n",
    "            c = set()\n",
    "            for i in a:\n",
    "                if i & s:\n",
    "                    c |= i\n",
    "                else:\n",
    "                    b.append(i)\n",
    "            ans += 1\n",
    "            if T in c:\n",
    "                return ans\n",
    "            a = b\n",
    "            s = c\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n",
    "        if S == T:\n",
    "            return 0\n",
    "        visited = []\n",
    "        will_visit = collections.deque()\n",
    "        route_count = len(routes)\n",
    "        distanse = {}\n",
    "        for index in range(route_count):\n",
    "            if S in routes[index]:\n",
    "                visited.append(index)\n",
    "                will_visit.append(index)\n",
    "                distanse[index] = 1\n",
    "        while (len(will_visit)>0):\n",
    "            cur_index = will_visit.popleft()\n",
    "            cur_bus = set(routes[cur_index])\n",
    "            if T in cur_bus:\n",
    "                return distanse[cur_index]\n",
    "            for i in range(route_count):\n",
    "                new_bus = set(routes[i])\n",
    "                if (i not in visited) and len(cur_bus & new_bus) > 0:\n",
    "                    visited.append(i)\n",
    "                    will_visit.append(i)\n",
    "                    distanse[i] = distanse[cur_index] + 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n",
    "        if not routes: return -1\n",
    "        if S == T: return 0\n",
    "        q = []\n",
    "        n = len(routes)\n",
    "        visited = {}\n",
    "        for i in range(n):\n",
    "            visited[i] = 0\n",
    "            if S in routes[i]:\n",
    "                visited[i] = 1\n",
    "                q.append((set(routes[i]), 1))\n",
    "        while q:\n",
    "            route, num_bus = q.pop(0)\n",
    "            if T in route:\n",
    "                return num_bus\n",
    "            for i in range(n):\n",
    "                if visited[i]:\n",
    "                    continue\n",
    "                if route & set(routes[i]):\n",
    "                    q.append((set(routes[i]), num_bus+1))\n",
    "                    visited[i] = 1\n",
    "        return -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:\n",
    "        if source == target:\n",
    "            return 0\n",
    "        que = []\n",
    "        i = 0\n",
    "        while i < len(routes):\n",
    "            if routes[i].count(target):\n",
    "                if routes[i].count(source):\n",
    "                    return 1\n",
    "                route = routes.pop(i)\n",
    "                route.remove(target)\n",
    "                que.append(route)\n",
    "            else:\n",
    "                i += 1\n",
    "        count = 2\n",
    "        que = sum(que, [])\n",
    "        while que:\n",
    "            temp = []\n",
    "            i = 0\n",
    "            while i < len(routes):\n",
    "                same=set(routes[i]) & set(que)\n",
    "                if same:\n",
    "                    if routes[i].count(source):\n",
    "                        return count\n",
    "                    route = routes.pop(i)\n",
    "                    for s in same:\n",
    "                        route.remove(s)\n",
    "                    temp.append(route)\n",
    "                else:\n",
    "                    i += 1\n",
    "            if len(temp) > 0:\n",
    "                count += 1\n",
    "                que = sum(temp, [])\n",
    "            else:\n",
    "                que = []\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n",
    "        if S == T:\n",
    "            return 0\n",
    "        dis = {}\n",
    "        start = []\n",
    "        end = []\n",
    "        neighbors = defaultdict(list)\n",
    "        for i in range(len(routes)):\n",
    "            if S in routes[i]:\n",
    "                start.append(i)\n",
    "            if T in routes[i]:\n",
    "                end.append(i)\n",
    "            for j in range(i+1, len(routes)):\n",
    "                if len(set(routes[i]).intersection(routes[j])) > 0:\n",
    "                    neighbors[i].append(j)\n",
    "                    neighbors[j].append(i)\n",
    "        if len(set(start).intersection(end)) > 0:\n",
    "            return 1\n",
    "        visited = defaultdict(int)\n",
    "        for s in start:\n",
    "            visited[s] = 1\n",
    "        queue = start\n",
    "        ans = 1\n",
    "        while len(queue) != 0:\n",
    "            size = len(queue)\n",
    "            for i in range(size):\n",
    "                curr = queue.pop(0)\n",
    "                visited[curr] = 1\n",
    "                if curr in end:\n",
    "                    return ans\n",
    "                for j in neighbors[curr]:\n",
    "                    if j not in visited:\n",
    "                        queue.append(j)\n",
    "            ans += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numBusesToDestination(self, routes, source, target) -> int:\n",
    "        if source==target:\n",
    "            return 0\n",
    "        path = []\n",
    "        i = 0\n",
    "        while(i<len(routes)):\n",
    "            if source in routes[i]:\n",
    "                if target in routes[i]:\n",
    "                    return 1\n",
    "                path.append((routes[i],1))\n",
    "                routes.pop(i)\n",
    "            else:\n",
    "                 i+=1\n",
    "        while(len(path)):\n",
    "            sr,index = path.pop(0)\n",
    "            i=0\n",
    "            while(i<len(routes)):\n",
    "                if len(list(set(routes[i]+sr)))<len(routes[i])+len(sr):\n",
    "                    if target in routes[i]:\n",
    "                        return index+1\n",
    "                    else:\n",
    "                        path.append((routes[i],index+1))\n",
    "                        routes.pop(i)\n",
    "                else:\n",
    "                        i+=1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numBusesToDestination(self, routes, source, target):\n",
    "        res=[]\n",
    "        res1=[]\n",
    "        if source==target:\n",
    "            return 0\n",
    "        for i in routes:\n",
    "            if source in i :\n",
    "                res1.append(i)\n",
    "        if not res1:\n",
    "            return 0\n",
    "        for i in res1:\n",
    "            if target in i:\n",
    "                return 1\n",
    "            routes.remove(i)\n",
    "        n=1\n",
    "        while res1:\n",
    "            size=len(res1)\n",
    "            if res:\n",
    "                break\n",
    "            for j in range(size):\n",
    "                a=res1.pop(0)\n",
    "                if target in a:\n",
    "                    res.append(n)\n",
    "                    break\n",
    "                for h in routes:\n",
    "                    if len(set(h+a))==len(h)+len(a):\n",
    "                        pass\n",
    "                    else:\n",
    "                        res1.append(h)\n",
    "            for i in res1:\n",
    "                if i in routes:\n",
    "                    routes.remove(i)\n",
    "            n+=1\n",
    "        if res:\n",
    "            return min(res)\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:\n",
    "        step = 1\n",
    "        begin = []\n",
    "        end = []\n",
    "        for i in routes:\n",
    "            if source in i:\n",
    "                begin.extend(i)\n",
    "            if target in i:\n",
    "                end.extend(i)\n",
    "        while begin and end:\n",
    "            if len(begin) < len(end):\n",
    "                begin, end = end, begin\n",
    "            next_stop = []\n",
    "            if target == source and target in begin:\n",
    "                return 0\n",
    "            if target in begin and target in end:\n",
    "                return step         \n",
    "            if len(set(begin)) + len(set(end)) > len(set(begin) | set(end)):\n",
    "                    return step + 1\n",
    "            for i in routes:\n",
    "                if len(set(begin)) + len(set(i)) > len(set(begin) | set(i)):\n",
    "                    next_stop.append(i)\n",
    "            begin = []\n",
    "            if next_stop:\n",
    "                step += 1\n",
    "                for i in next_stop:\n",
    "                    routes.remove(i)\n",
    "                    begin.extend(i)\n",
    "        return -1\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:\n",
    "        if source == target:\n",
    "            return 0\n",
    "        edges = defaultdict(set)\n",
    "        def help(a,b):\n",
    "            return len(a)+len(b) != len(set(a+b))\n",
    "        begin,end = -1,-1\n",
    "        for i,a in enumerate(routes):\n",
    "            if source in a and target in a:\n",
    "                return 1\n",
    "            if source in a:\n",
    "                begin = i\n",
    "            if target in a:\n",
    "                end = i\n",
    "            edges[i].add(i)\n",
    "            for j,b in enumerate(routes):\n",
    "                if i!=j and help(a,b):\n",
    "                    edges[i].add(j)\n",
    "                    edges[j].add(i)\n",
    "        if begin == -1 or end == -1:\n",
    "            return -1\n",
    "        if begin == end:\n",
    "            return 1\n",
    "        p = [begin]\n",
    "        have = set()\n",
    "        have.add(begin)\n",
    "        ans = 1\n",
    "        while p:\n",
    "            ans += 1\n",
    "            q = []\n",
    "            for node in p:\n",
    "                for num in edges[node]:\n",
    "                    if num == end:\n",
    "                        return ans\n",
    "                    if num not in have:\n",
    "                        q.append(num)\n",
    "                        have.add(num)\n",
    "            p = q\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:\n",
    "        if source == target: return 0           #如果起点恰是终点，不用换乘\n",
    "        n = len(routes)\n",
    "        rmap = [[0] * n for _ in range(n)]      #邻接表\n",
    "        start, end = set(), set()               #起点和终点所在的班线序号\n",
    "        for i, route in enumerate(routes):      #遍历一遍所有班线\n",
    "            routes[i] = set(route)              #并以哈希表的形式存储每个班线中的站点\n",
    "            if source in routes[i]:             #找出起点所在的班线序号\n",
    "                start.add(i)\n",
    "            if target in routes[i]:             #找出起点所在的班线序号\n",
    "                end.add(i)\n",
    "            if start and start & end:           #如果起点和终点同属一条班线\n",
    "                return 1                        #只需要搭乘一次\n",
    "        if not start or not end: return -1      #起点或终点不在任何班线中，返回-1\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1, n):             #构建邻接表\n",
    "                if routes[i] & routes[j]:       #如果两班线有公共站点\n",
    "                    rmap[i][j] = rmap[j][i] = 1 #两班线之间的状态为可达\n",
    "\n",
    "        q = collections.deque([s for s in start])         \n",
    "        visit = Counter(start)                  #记录访问状态及路径长度的哈希表\n",
    "        while q:\n",
    "            cur = q.popleft()\n",
    "            cnt = visit[cur]\n",
    "            if cur in end:                      #找到终点所在班线，停止\n",
    "                return cnt\n",
    "            for i in range(n):                  #放入当前班线可达且没访问过的班线\n",
    "                if rmap[cur][i] and i not in visit:\n",
    "                    q.append(i)\n",
    "                    visit[i] = cnt + 1          #并将其路径长度设为当前长度+1\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:\n",
    "        if source==target:\n",
    "            return 0\n",
    "        des=[]\n",
    "        start=[]\n",
    "        m=len(routes)\n",
    "        visited=[False]*m\n",
    "        for i in range(m):\n",
    "            flag=False\n",
    "            if source in routes[i]:\n",
    "                start.append(i)\n",
    "                flag=True\n",
    "            if target in routes[i]:\n",
    "                des.append(i)\n",
    "                if flag==True:\n",
    "                    return 1\n",
    "        que=deque(start)\n",
    "        ans=1\n",
    "        while que:\n",
    "            ans+=1\n",
    "            size=len(que)\n",
    "            for _ in range(size):\n",
    "                now=que.popleft()\n",
    "                length=len(routes[now])\n",
    "                visited[now]=True\n",
    "                for r in range(m):\n",
    "                    if not visited[r] and routes[r][0]<=routes[now][-1] and routes[r][-1]>=routes[now][0]:\n",
    "                        for j in range(length):\n",
    "                            if routes[now][j] in routes[r]:\n",
    "                                if r in des:\n",
    "                                    return ans\n",
    "                                que.append(r)\n",
    "                                visited[r]=True\n",
    "                                break\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numBusesToDestination(self, routes: list[list[int]], source: int, target: int) -> int:\n",
    "        if source == target:\n",
    "            return 0\n",
    "        n = len(routes)\n",
    "        res = 1\n",
    "        visited = [False] * n\n",
    "        sourcerlist = []\n",
    "        targetrlist = []\n",
    "        for i in range(n):\n",
    "            flag = False\n",
    "            if target in routes[i]:\n",
    "                flag = True\n",
    "                targetrlist.append(i)\n",
    "            if source in routes[i]:\n",
    "                if flag:\n",
    "                    return 1\n",
    "                sourcerlist.append(i)\n",
    "        print(targetrlist)\n",
    "        print(sourcerlist)\n",
    "        que = deque()\n",
    "        que += targetrlist\n",
    "        while que:\n",
    "            res += 1\n",
    "            size = len(que)\n",
    "            for i in range(size):\n",
    "                now = que.popleft()\n",
    "                visited[now] = True\n",
    "                ll = len(routes[now])\n",
    "                for r in range(n):\n",
    "                    if (not visited[r]) and routes[r][-1] >= routes[now][0]:\n",
    "                        for j in range(ll):\n",
    "                            if routes[now][j] in routes[r]:\n",
    "                                if r in sourcerlist:\n",
    "                                    return res\n",
    "                                else:\n",
    "                                    que.append(r)\n",
    "                                    visited[r] = True\n",
    "                                    break\n",
    "        return -1\n",
    "            \n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    obj = Solution()\n",
    "    routes = [[0, 1, 6, 16, 22, 23], [14, 15, 24, 32], [4, 10, 12, 20, 24, 28, 33], [1, 10, 11, 19, 27, 33],\n",
    "              [11, 23, 25, 28], [15, 20, 21, 23, 29], [29]]\n",
    "    source = 4\n",
    "    target = 21\n",
    "    print(obj.numBusesToDestination(routes, source, target))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:\n",
    "        if source == target: return 0           #如果起点恰是终点，不用换乘\n",
    "        n = len(routes)\n",
    "        rmap = [[0] * n for _ in range(n)]      #邻接表\n",
    "        start, end = set(), set()               #起点和终点所在的班线序号\n",
    "        for i, route in enumerate(routes):      #遍历一遍所有班线\n",
    "            routes[i] = set(route)              #并以哈希表的形式存储每个班线中的站点\n",
    "            if source in routes[i]:             #找出起点所在的班线序号\n",
    "                start.add(i)\n",
    "            if target in routes[i]:             #找出起点所在的班线序号\n",
    "                end.add(i)\n",
    "            if start and start & end:           #如果起点和终点同属一条班线\n",
    "                return 1                        #只需要搭乘一次\n",
    "        if not start or not end: return -1      #起点或终点不在任何班线中，返回-1\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1, n):             #构建邻接表\n",
    "                if routes[i] & routes[j]:       #如果两班线有公共站点\n",
    "                    rmap[i][j] = rmap[j][i] = 1 #两班线之间的状态为可达\n",
    "\n",
    "        q = collections.deque([s for s in start])         \n",
    "        visit = Counter(start)                  #记录访问状态及路径长度的哈希表\n",
    "        while q:\n",
    "            cur = q.popleft()\n",
    "            cnt = visit[cur]\n",
    "            if cur in end:                      #找到终点所在班线，停止\n",
    "                return cnt\n",
    "            for i in range(n):                  #放入当前班线可达且没访问过的班线\n",
    "                if rmap[cur][i] and i not in visit:\n",
    "                    q.append(i)\n",
    "                    visit[i] = cnt + 1          #并将其路径长度设为当前长度+1\n",
    "        return -1                               #结束时仍未找到，返回-1\n",
    "\n",
    "\n",
    "        \n",
    "        \n",
    "       \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:\n",
    "        step = 1\n",
    "        begin = []\n",
    "        end = []\n",
    "        for i in routes:\n",
    "            if source in i:\n",
    "                begin.extend(i)\n",
    "            if target in i:\n",
    "                end.extend(i)\n",
    "        while begin and end:\n",
    "            routes1 = copy.deepcopy(routes)\n",
    "            if len(begin) < len(end):\n",
    "                begin, end = end, begin\n",
    "            if target == source and target in begin:\n",
    "                return 0\n",
    "            if target in begin and target in end:\n",
    "                return step         \n",
    "            if len(set(begin)) + len(set(end)) > len(set(begin) | set(end)):\n",
    "                    return step + 1\n",
    "            next_stop = []\n",
    "            for i in routes:\n",
    "                if len(set(begin)) + len(set(i)) > len(set(begin) | set(i)):\n",
    "                    next_stop.extend(i)\n",
    "                    routes1.remove(i)\n",
    "            if next_stop:\n",
    "                step += 1\n",
    "            begin = next_stop\n",
    "            routes = routes1\n",
    "\n",
    "        return -1\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:\n",
    "        if source == target: return 0           #如果起点恰是终点，不用换乘\n",
    "        n = len(routes)\n",
    "        rmap = [[0] * n for _ in range(n)]      #邻接表\n",
    "        start, end = set(), set()               #起点和终点所在的班线序号\n",
    "        for i, route in enumerate(routes):      #遍历一遍所有班线\n",
    "            routes[i] = set(route)              #并以哈希表的形式存储每个班线中的站点\n",
    "            if source in routes[i]:             #找出起点所在的班线序号\n",
    "                start.add(i)\n",
    "            if target in routes[i]:             #找出起点所在的班线序号\n",
    "                end.add(i)\n",
    "            if start and start & end:           #如果起点和终点同属一条班线\n",
    "                return 1                        #只需要搭乘一次\n",
    "        if not start or not end: return -1      #起点或终点不在任何班线中，返回-1\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1, n):             #构建邻接表\n",
    "                if routes[i] & routes[j]:       #如果两班线有公共站点\n",
    "                    rmap[i][j] = rmap[j][i] = 1 #两班线之间的状态为可达\n",
    "\n",
    "        q = collections.deque([s for s in start])         \n",
    "        visit = Counter(start)                  #记录访问状态及路径长度的哈希表\n",
    "        while q:\n",
    "            cur = q.popleft()\n",
    "            cnt = visit[cur]\n",
    "            if cur in end:                      #找到终点所在班线，停止\n",
    "                return cnt\n",
    "            for i in range(n):                  #放入当前班线可达且没访问过的班线\n",
    "                if rmap[cur][i] and i not in visit:\n",
    "                    q.append(i)\n",
    "                    visit[i] = cnt + 1          #并将其路径长度设为当前长度+1\n",
    "        return -1                               #结束时仍未找到，返回-1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:\n",
    "        queue = []\n",
    "        hashmap = []\n",
    "        if source == target:\n",
    "            return 0\n",
    "        # 转为hash表\n",
    "        for i in range(len(routes)):\n",
    "            hashmap.append(set(routes[i]))\n",
    "\n",
    "        #初始站点可能有好几条线，可以选择任意一条\n",
    "        for i in range(len(hashmap)):\n",
    "            if source in hashmap[i]:\n",
    "                queue.append(i)\n",
    "        visited = set(queue)\n",
    "        step = 0\n",
    "        while queue:\n",
    "            current_size = len(queue)\n",
    "            for cur in range(current_size):\n",
    "                ind = queue.pop(0)\n",
    "                if target in hashmap[ind]:\n",
    "                    return step+1\n",
    "                #将多条线入队\n",
    "                for i in range(len(routes)):\n",
    "                    if i not in visited:\n",
    "                        # 一条线上的每一个站点\n",
    "                        for j in  range(len(routes[i])):\n",
    "                            if routes[i][j] in hashmap[ind]:\n",
    "                                queue.append(i)\n",
    "                                visited.add(i)\n",
    "            step += 1 \n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:\n",
    "        if source == target:\n",
    "            return 0\n",
    "\n",
    "        routes = [set(route) for route in routes]\n",
    "        queue = deque()\n",
    "        visited = set()\n",
    "\n",
    "        for i, route in enumerate(routes):\n",
    "            if source in route:\n",
    "                route.remove(source)\n",
    "                queue.append((route, 1))\n",
    "                visited.add(i)\n",
    "\n",
    "        while queue:\n",
    "            route, count = queue.popleft()\n",
    "            for station in route:\n",
    "                if station == target:\n",
    "                    return count\n",
    "                for i, r in enumerate(routes):\n",
    "                    if i not in visited and station in r:\n",
    "                        r.remove(station)\n",
    "                        queue.append((r, count + 1))\n",
    "                        visited.add(i)\n",
    "\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:\n",
    "        if source == target:\n",
    "            return 0\n",
    "        adjacency = defaultdict(list)\n",
    "        n = len(routes)\n",
    "        tmp, queue, res = [], [], 0\n",
    "        visited = set()\n",
    "        for route in routes:\n",
    "            tmp.append(set(route))\n",
    "        for i in range(n):\n",
    "            if source in tmp[i]:\n",
    "                queue.append(i)\n",
    "                visited.add(i)\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1, n):\n",
    "                for k in range(len(routes[i])):\n",
    "                    if routes[i][k] in tmp[j]:\n",
    "                        adjacency[j].append(i)\n",
    "                        adjacency[i].append(j)\n",
    "                        break\n",
    "        while queue:\n",
    "            size = len(queue)\n",
    "            for _ in range(size):\n",
    "                cur = queue.pop(0)\n",
    "                if target in tmp[cur]:\n",
    "                    return res + 1\n",
    "                for next_route in adjacency[cur]:\n",
    "                    if next_route in visited:\n",
    "                        continue\n",
    "                    queue.append(next_route)\n",
    "                    visited.add(next_route)\n",
    "            res += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numBusesToDestination(self, r: List[List[int]], s: int, t: int) -> int:\n",
    "        if s==t:\n",
    "            return 0 \n",
    "        n = len(r)\n",
    "        a = {j:set(r[j]) for j in range(n)} \n",
    "        g = [[] for _ in range(n)] \n",
    "        for j in range(n):\n",
    "            for k in range(n):\n",
    "                if j!=k:\n",
    "                    if a[j]&a[k]:\n",
    "                        g[j].append(k) \n",
    "        v = {}\n",
    "        st = []\n",
    "        end = []\n",
    "        for j in a:\n",
    "            if s in a[j]:\n",
    "                v[j] = 1 \n",
    "                st.append(j) \n",
    "            if t in a[j]:\n",
    "                end.append(j)\n",
    "        while st:\n",
    "            tmp = []\n",
    "            for j in st:\n",
    "                for k in g[j]:\n",
    "                    if k not in v:\n",
    "                        v[k] = v[j] + 1 \n",
    "                        tmp.append(k)\n",
    "            st = tmp  \n",
    "        # print(v, end)\n",
    "        ans = 10**9 \n",
    "        for j in end:\n",
    "            if j in v:\n",
    "                ans = min(ans, v[j]) \n",
    "        return ans if ans<10**9 else -1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:\n",
    "        e=collections.defaultdict(list)\n",
    "        n=len(routes)\n",
    "        ls=[set() for _ in range(n)]\n",
    "        find=[False]*n\n",
    "        q=collections.deque()\n",
    "        if source==target:\n",
    "            return 0\n",
    "        for i,r in enumerate(routes):\n",
    "            for c in r:\n",
    "                ls[i].add(c)\n",
    "                if c==source:\n",
    "                    find[i]=True\n",
    "                    q.append((1,i))\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                if ls[i]&ls[j]:\n",
    "                    e[i].append(j)\n",
    "                    e[j].append(i)\n",
    "        while q:\n",
    "            d,now=q.popleft()\n",
    "            if target in ls[now]:\n",
    "                return d\n",
    "            for i in e[now]:\n",
    "                if find[i]:\n",
    "                    continue\n",
    "                find[i]=True\n",
    "                q.append((d+1,i))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def get_set(self,groups:List[int],routes: List[List[int]])->set:\n",
    "\n",
    "        temp=set()\n",
    "        for group in groups:\n",
    "            temp_attr=routes[group]\n",
    "            for station in temp_attr:\n",
    "                temp.add(station)\n",
    "        return temp\n",
    "\n",
    "\n",
    "    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:\n",
    "        \n",
    "        if source==target:\n",
    "            return 0\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        size=len(routes)\n",
    "        cross_marked =dict()\n",
    "        source_groups=set()\n",
    "        target_groups=set()\n",
    "        for i in range(size):\n",
    "            group_i=set(routes[i])\n",
    "            if source in group_i:\n",
    "                source_groups.add(i)\n",
    "            if target in group_i:\n",
    "                target_groups.add(i)\n",
    "            for j in range(size):\n",
    "                if i==j :\n",
    "                    continue\n",
    "                group_j=set(routes[j])\n",
    "                if not group_i.isdisjoint(group_j):\n",
    "                    if i in cross_marked.keys():\n",
    "                        temp=cross_marked.get(i)\n",
    "                        temp.append(j)\n",
    "                        cross_marked[i]=temp\n",
    "                    else:\n",
    "                        temp=[]\n",
    "                        temp.append(j)\n",
    "                        cross_marked[i]=temp\n",
    "                    if j in cross_marked.keys():\n",
    "                        temp=cross_marked.get(j)\n",
    "                        temp.append(i)\n",
    "                        cross_marked[j]=temp\n",
    "                    else:\n",
    "                        temp=[]\n",
    "                        temp.append(i)\n",
    "                        cross_marked[j]=temp\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        if len(source_groups)==0 or len(target_groups)==0:\n",
    "            return -1\n",
    "        \n",
    "        if not source_groups.isdisjoint(target_groups):\n",
    "            return 1\n",
    "        \n",
    "        if len(cross_marked)==0:\n",
    "            return -1\n",
    "\n",
    "        stations=cross_marked.keys()\n",
    "        min_id=min(stations)\n",
    "        max_id=max(stations)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        n=max_id-min_id+1\n",
    "\n",
    "        visited=[0 for _ in range(n)]\n",
    "\n",
    "        que=[source_groups]\n",
    "\n",
    "        is_Find=False\n",
    "        level=1\n",
    "\n",
    "\n",
    "\n",
    "        while que:\n",
    "            temp_set=que.pop()\n",
    "            if not temp_set.isdisjoint(target_groups):\n",
    "                is_Find=True\n",
    "                break\n",
    "\n",
    "            station_set=[]\n",
    "            for temp_station in temp_set:\n",
    "                if visited[temp_station-min_id]!=0:\n",
    "                    continue\n",
    "                groups=cross_marked.get(temp_station)\n",
    "                station_set.extend(groups)\n",
    "                visited[temp_station - min_id] = 1\n",
    "\n",
    "            temp_size=len(station_set)\n",
    "            level += 1\n",
    "            if temp_size==0:\n",
    "                break\n",
    "            que.append(set(station_set))\n",
    "\n",
    "\n",
    "\n",
    "        if not is_Find:\n",
    "            return -1\n",
    "        else:\n",
    "            return level\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:\n",
    "        if source == target:\n",
    "            return 0\n",
    "        n = len(routes)\n",
    "        visit_bus = set()\n",
    "        visit_station = set()\n",
    "        routes = [set(route) for route in routes]\n",
    "        q = deque([(source,0)])\n",
    "        while q:\n",
    "            cur, ans = q.popleft()\n",
    "            if cur == target:\n",
    "                return ans\n",
    "            for i, route in enumerate(routes):\n",
    "                if i not in visit_bus:\n",
    "                    if cur in route:\n",
    "                        for station in route-visit_station:\n",
    "                            q.append((station, ans+1))\n",
    "                            visit_station.add(station)\n",
    "                        visit_bus.add(i)\n",
    "        return -1\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "        \n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:\n",
    "        if source == target:\n",
    "            return 0\n",
    "        n = len(routes)\n",
    "        nei = [[] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                routes[i] = set(routes[i])\n",
    "                routes[j] = set(routes[j])\n",
    "                if routes[i] & routes[j]:\n",
    "                    nei[i].append(j)\n",
    "                    nei[j].append(i)\n",
    "        start = set()\n",
    "        end = set()\n",
    "        for i in range(n):\n",
    "            if source in routes[i]:\n",
    "                start.add(i)\n",
    "            if target in routes[i]:\n",
    "                end.add(i)\n",
    "        q = collections.deque(start)\n",
    "        visited = start\n",
    "        step = 1\n",
    "        while q:\n",
    "            l = len(q)\n",
    "            for i in range(l):\n",
    "                cur = q.popleft()\n",
    "                if cur in end:\n",
    "                    return step\n",
    "                for nxt in nei[cur]:\n",
    "                    if nxt not in visited:\n",
    "                        visited.add(nxt)\n",
    "                        q.append(nxt)\n",
    "            step += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:\n",
    "        if source == target:\n",
    "            return 0\n",
    "        # 建立hashmap {stop:[route]} 记录每个站点有哪些线路可以到达\n",
    "        hmap = {}\n",
    "        for i in range(len(routes)):\n",
    "            for stop in routes[i]:\n",
    "                hmap[stop] = hmap.get(stop, []) + [i]\n",
    "\n",
    "        # 栈,记录线路. 初始状态记录出发站所属的线路\n",
    "        # 每一轮(每次乘车),检查弹出的站内线路, 遍历该线路的所有站点\n",
    "        # 如果发现目标站点,直接返回换乘车次数,如果没有发现,将所遍历到站点所属的线路加入栈\n",
    "        stk = deque(hmap[source])\n",
    "        res = 1\n",
    "        used = set()  # 记录坐过的线路\n",
    "        while stk:\n",
    "            for _ in range(len(stk)):\n",
    "                curRoute = stk.popleft()\n",
    "                if curRoute in used:\n",
    "                    continue\n",
    "                used.add(curRoute)\n",
    "                # 检查当前线路上的站点\n",
    "                for stop in routes[curRoute]:\n",
    "                    # 发现目标站就返回\n",
    "                    if stop == target:\n",
    "                        return res\n",
    "                    for route in hmap[stop]:\n",
    "                        if route in used:\n",
    "                            continue\n",
    "                        stk.append(route)\n",
    "            res += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numBusesToDestination(self, routes, source: int, target: int) -> int:\n",
    "        if target == source:\n",
    "            return 0\n",
    "        stop = {}\n",
    "        for i in range(len(routes)):\n",
    "            for j in range(len(routes[i])):\n",
    "                stop[routes[i][j]] = stop.get(routes[i][j],[]) + [i]\n",
    "        r_tmp = []\n",
    "        for i in range(len(routes)):\n",
    "            tmp = []\n",
    "            for j in range(len(routes[i])):\n",
    "                if len(stop[routes[i][j]])==1 and routes[i][j] != target and routes[i][j] != source:\n",
    "                    del stop[routes[i][j]]\n",
    "                else:\n",
    "                    tmp += [routes[i][j]]\n",
    "            r_tmp += [tmp]\n",
    "        routes = r_tmp\n",
    "        s1 = [source]\n",
    "        leng = 0\n",
    "        bus = []\n",
    "        p1 = 0\n",
    "        p2 = 0\n",
    "        while(1):\n",
    "            if p1 == len(s1):\n",
    "                return -1\n",
    "            for i in range(p1,len(s1)):\n",
    "                for j in range(len(stop.get(s1[i],[]))):\n",
    "                    if stop[s1[i]][j] not in bus:\n",
    "                        bus += [stop[s1[i]][j]]\n",
    "            leng += 1\n",
    "            p1 = len(s1)\n",
    "            if p2 == len(bus):\n",
    "                return -1\n",
    "            for i in range(p2,len(bus)):\n",
    "                for j in range(len(routes[bus[i]])):\n",
    "                    if routes[bus[i]][j] not in s1:\n",
    "                        if routes[bus[i]][j] == target:\n",
    "                            return leng\n",
    "                        else:\n",
    "                            s1 += [routes[bus[i]][j]]\n",
    "            p2 = len(bus)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque \n",
    "class Solution:\n",
    "    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:\n",
    "        if source==target: return 0\n",
    "        m=defaultdict(list)\n",
    "        for idx, route in enumerate(routes):\n",
    "            for stop in route:\n",
    "                m[stop].append(idx)\n",
    "        visited=[0 for _ in range(len(routes))]\n",
    "        q=deque([source])\n",
    "        buses=0\n",
    "        while q:\n",
    "            size=len(q)\n",
    "            buses+=1\n",
    "            for _ in range(size):\n",
    "                cur=q.popleft()\n",
    "                for r in m[cur]:\n",
    "                    if visited[r]:\n",
    "                        continue\n",
    "                    else:\n",
    "                        visited[r]=1\n",
    "                        for stop in routes[r]:\n",
    "                            if stop == target:\n",
    "                                return buses\n",
    "                            else:\n",
    "                                q.append(stop)\n",
    "        return -1\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numBusesToDestination(\n",
    "        self, routes: List[List[int]], source: int, target: int\n",
    "    ) -> int:\n",
    "        if source == target:\n",
    "            return 0\n",
    "        mp = defaultdict(list)\n",
    "        for i, route in enumerate(routes):\n",
    "            ok1 = ok2 = False\n",
    "            for x in route:\n",
    "                mp[x].append(i)\n",
    "                if x == source:\n",
    "                    ok1 = True\n",
    "                elif x == target:\n",
    "                    ok2 = True\n",
    "            if ok1 and ok2:\n",
    "                return 1\n",
    "        n = len(routes)\n",
    "        dist = [inf] * n\n",
    "        q = mp[source].copy()\n",
    "        mp[source].clear()\n",
    "        if not q:\n",
    "            return -1\n",
    "        for x in q:\n",
    "            dist[x] = 1\n",
    "\n",
    "        while q:\n",
    "            nxt = []\n",
    "            for x in q:\n",
    "                for y in routes[x]:\n",
    "                    for z in mp[y]:\n",
    "                        if dist[z] == inf:\n",
    "                            dist[z] = dist[x] + 1\n",
    "                            nxt.append(z)\n",
    "                        if y == target:\n",
    "                            return dist[z]\n",
    "                    mp[y].clear()\n",
    "            q = nxt\n",
    "        return -1\n",
    "\n",
    "        # g = defaultdict(list)\n",
    "        # for route in routes:\n",
    "        #     for x, y in pairwise(route):\n",
    "        #         g[x].append(y)\n",
    "        #     g[route[-1]].append(route[0])\n",
    "\n",
    "        # dist = defaultdict(lambda: inf)\n",
    "\n",
    "        # q = [(0, source)]\n",
    "        # while q:\n",
    "        #     d, x = heappop(q)\n",
    "        #     if x == target:\n",
    "        #         return d\n",
    "        #     for y in g[x]:\n",
    "        #         if d + 1 < dist[y]:\n",
    "        #             dist[y] = d + 1\n",
    "        #             heappush(q, (dist[y], y))\n",
    "        # return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:\n",
    "        if source == target:\n",
    "            return 0\n",
    "        s_routes = defaultdict(list)\n",
    "        n = len(routes)\n",
    "        connected = [[False]*n for _ in range(n)]\n",
    "        for r1, route in enumerate(routes):\n",
    "            for site in route:\n",
    "                for r2 in s_routes[site]:\n",
    "                    connected[r1][r2] = connected[r2][r1] = True\n",
    "                s_routes[site].append(r1)\n",
    "        if not s_routes[target]:\n",
    "            return -1\n",
    "        dists = [inf]*n\n",
    "        q = deque(s_routes[source])\n",
    "        for r in s_routes[source]:\n",
    "            dists[r] = 1\n",
    "        while q:\n",
    "            r1 = q.popleft()\n",
    "            for r2 in range(n):\n",
    "                if connected[r1][r2] and dists[r2] == inf:\n",
    "                    dists[r2] = dists[r1]+1\n",
    "                    q.append(r2)\n",
    "        res = min((dists[r] for r in s_routes[target]))\n",
    "        if res == inf:\n",
    "            return -1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:\n",
    "        if source == target: return 0\n",
    "        n = len(routes)  # treat each route as a node\n",
    "        stop2route = defaultdict(list)\n",
    "        for i in range(n):\n",
    "            routes[i] = set(routes[i])\n",
    "            for stop in routes[i]:\n",
    "                stop2route[stop].append(i)\n",
    "        dq = deque()\n",
    "        vis = [False] * n\n",
    "        for i, route in enumerate(routes):\n",
    "            if source in route:\n",
    "                dq.append((i, 1))\n",
    "                vis[i] = True\n",
    "        while dq:\n",
    "            i, step = dq.popleft()\n",
    "            route = routes[i]\n",
    "            if target in route: return step\n",
    "            for stop in route:\n",
    "                for to_route in stop2route[stop]:\n",
    "                    if not vis[to_route]:\n",
    "                        vis[to_route] = True\n",
    "                        dq.append((to_route, step+1))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:\n",
    "        dic = {}\n",
    "        seen = set()\n",
    "        seenst = set()\n",
    "        queue = deque()\n",
    "        h = 999999\n",
    "        for i in range(len(routes)):\n",
    "            for k in range(len(routes[i])):\n",
    "                if dic.get(routes[i][k]):\n",
    "                    dic[routes[i][k]].append(i)\n",
    "                elif not dic.get(routes[i][k]):\n",
    "                    dic[routes[i][k]] = [i]\n",
    "                if routes[i][k] == source and not queue:\n",
    "                    queue.append([routes[i][k],i,0])\n",
    "        seen.add(source)\n",
    "        ff = 0\n",
    "        if source == target:\n",
    "            h = 0\n",
    "        elif dic.get(source) and dic.get(target):\n",
    "            q = 0\n",
    "            while queue:\n",
    "                station,nums,n = queue.popleft()\n",
    "                l = dic.get(station)\n",
    "                n += 1\n",
    "                for f in l:\n",
    "                    if f not in seenst:\n",
    "                        ll = routes[f]\n",
    "                        for g in range(len(ll)):\n",
    "                            if ll[g] not in seen and ll[g] != target:\n",
    "                                seen.add(ll[g])\n",
    "                                queue.append([ll[g],f,n])\n",
    "                            if ll[g] == target:\n",
    "                                q = n\n",
    "                                ff = 1\n",
    "                                h = min(h,n)\n",
    "                    seenst.add(f)\n",
    "                if n == q and ff == 1:\n",
    "                    break\n",
    "            if ff == 0:\n",
    "                h = -1\n",
    "        else:\n",
    "            h = -1\n",
    "        return h"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:\n",
    "\n",
    "        if source == target:\n",
    "            return 0\n",
    "\n",
    "        stopToRoute = {}\n",
    "        for idx, route in enumerate(routes):\n",
    "            for stop in route:\n",
    "                # {1:[0,1,2], etc}\n",
    "                stopToRoute.setdefault(stop,[]).append(idx)\n",
    "\n",
    "        queue = deque([(source, 0)]) # stop, bus_count\n",
    "        visited_routes = set()\n",
    "\n",
    "        while queue:\n",
    "            \n",
    "            stop, bus_count = queue.popleft()\n",
    "\n",
    "            if stop == target:\n",
    "                return bus_count\n",
    "\n",
    "            # [0,1,2]\n",
    "            for route in stopToRoute.get(stop,[]):\n",
    "\n",
    "                if route not in visited_routes:\n",
    "                    visited_routes.add(route)\n",
    "                    \n",
    "                    for stop in routes[route]:\n",
    "\n",
    "                        queue.append((stop, bus_count+1))\n",
    "\n",
    "        return -1\n",
    "                    \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:\n",
    "        if source == target:\n",
    "            return 0\n",
    "\n",
    "        station2Route = {}\n",
    "        for routeId, route in enumerate(routes):\n",
    "            for station in route:\n",
    "                if station not in station2Route:\n",
    "                    station2Route[station] = []\n",
    "                station2Route[station].append(routeId)\n",
    "        \n",
    "        if source not in station2Route:\n",
    "            return -1\n",
    "        if target not in station2Route:\n",
    "            return -1\n",
    "        \n",
    "        queue = deque()\n",
    "        queue.append((source, 0))\n",
    "        visited = set([source])\n",
    "        while queue:\n",
    "            curStation, step = queue.popleft()\n",
    "            if curStation == target:\n",
    "                return step\n",
    "            for routeId in station2Route[curStation]:\n",
    "                route = routes[routeId]\n",
    "                for station in route:\n",
    "                    if station not in visited:\n",
    "                        visited.add(station)\n",
    "                        queue.append((station, step + 1))\n",
    "\n",
    "        \n",
    "        return -1\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:\n",
    "        if source == target:\n",
    "            return 0\n",
    "            \n",
    "        busToStop = defaultdict(set)\n",
    "        stopToBus = defaultdict(list)\n",
    "        visited = [False] * len(routes)\n",
    "        busToBus = defaultdict(set)\n",
    "        for i in range(len(routes)):\n",
    "            busToStop[i] = set(routes[i])\n",
    "            for s in routes[i]:\n",
    "                stopToBus[s].append(i)\n",
    "\n",
    "        for bus in busToStop:\n",
    "            for s in busToStop[bus]:\n",
    "                for b in stopToBus[s]:\n",
    "                    if b != bus:\n",
    "                        busToBus[bus].add(b)\n",
    "        \n",
    "        \n",
    "        res = 0\n",
    "        queue = deque(stopToBus[source])\n",
    "        while queue:\n",
    "            res += 1\n",
    "            for _ in range(len(queue)):\n",
    "                route = queue.popleft()\n",
    "                if target in busToStop[route]:\n",
    "                    return res\n",
    "                else:\n",
    "                    for b in busToBus[route]:\n",
    "                        if not visited[b]:\n",
    "                            visited[b] = True\n",
    "                            queue.append(b)\n",
    "\n",
    "        \n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\r\n",
    "class Solution:\r\n",
    "    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:\r\n",
    "        if source==target:\r\n",
    "            return 0\r\n",
    "        s=[False]*len(routes)\r\n",
    "        t=[False]*len(routes)\r\n",
    "        stop1={}\r\n",
    "        stop2={}\r\n",
    "        v=collections.defaultdict(lambda:[])\r\n",
    "        for i in range(len(routes)):\r\n",
    "            for j in routes[i]:\r\n",
    "                v[j].append(i)\r\n",
    "        h1=0\r\n",
    "        h2=0\r\n",
    "        p1=[source]\r\n",
    "        p2=[]\r\n",
    "        q1=[target]\r\n",
    "        q2=[]\r\n",
    "        while p1 and q1:\r\n",
    "            while p1:\r\n",
    "                place=p1[0]\r\n",
    "                del p1[0]\r\n",
    "                for i in v[place]:\r\n",
    "                    if not s[i]:\r\n",
    "                        s[i]=True\r\n",
    "                        if t[i]:\r\n",
    "                            return h1+h2\r\n",
    "                        for j in routes[i]:\r\n",
    "                            if j not in stop1:\r\n",
    "                                stop1[j]=True\r\n",
    "                                p2.append(j)\r\n",
    "            if p2:\r\n",
    "                p1=p2\r\n",
    "                p2=[]\r\n",
    "                h1+=1\r\n",
    "            else:\r\n",
    "                return -1\r\n",
    "            while q1:\r\n",
    "                place=q1[0]\r\n",
    "                del q1[0]\r\n",
    "                for i in v[place]:\r\n",
    "                    if not t[i]:\r\n",
    "                        t[i]=True\r\n",
    "                        if s[i]:\r\n",
    "                            return h1+h2\r\n",
    "                        for j in routes[i]:\r\n",
    "                            if j not in stop2:\r\n",
    "                                stop2[j]=True\r\n",
    "                                q2.append(j)\r\n",
    "            if q2:\r\n",
    "                q1=q2\r\n",
    "                q2=[]\r\n",
    "                h2+=1\r\n",
    "            else:\r\n",
    "                return -1\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:\n",
    "        g = defaultdict(list) # stop: [bus]\n",
    "        for bus, route in enumerate(routes):\n",
    "            for stop in route:\n",
    "                g[stop].append(bus)\n",
    "        \n",
    "        q = deque([(source, 0)])\n",
    "        buses = [set(r) for r in routes]\n",
    "        visited_bus, visited_stop = set(), set([source])\n",
    "        while q:\n",
    "            stop, cost = q.popleft()\n",
    "            if stop == target:\n",
    "                return cost\n",
    "            for bus in g[stop]:\n",
    "                if bus not in visited_bus:\n",
    "                    visited_bus.add(bus)\n",
    "                    for s in buses[bus]:\n",
    "                        if s not in visited_stop:\n",
    "                            # visited_stop.add(s)\n",
    "                            q.append((s, cost + 1))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:\n",
    "        g = defaultdict(list) # stop: [bus]\n",
    "        for bus, route in enumerate(routes):\n",
    "            for stop in route:\n",
    "                g[stop].append(bus)\n",
    "        \n",
    "        q = deque([(source, 0)])\n",
    "        buses = [set(r) for r in routes]\n",
    "        visited_bus, visited_stop = set(), set([source])\n",
    "        while q:\n",
    "            stop, cost = q.popleft()\n",
    "            if stop == target:\n",
    "                return cost\n",
    "            for bus in g[stop]:\n",
    "                if bus not in visited_bus:\n",
    "                    visited_bus.add(bus)\n",
    "                    for s in buses[bus]:\n",
    "                        if s not in visited_stop:\n",
    "                            visited_stop.add(s)\n",
    "                            q.append((s, cost + 1))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:\n",
    "        g = defaultdict(list) # stop: [bus]\n",
    "        for bus, route in enumerate(routes):\n",
    "            for stop in route:\n",
    "                g[stop].append(bus)\n",
    "        \n",
    "        q = deque([(source, 0)])\n",
    "        buses = [set(r) for r in routes]\n",
    "        visited_bus, visited_stop = set(), set([source])\n",
    "        while q:\n",
    "            stop, cost = q.popleft()\n",
    "            if stop == target:\n",
    "                return cost\n",
    "            for bus in g[stop]:\n",
    "                if bus not in visited_bus:\n",
    "                    visited_bus.add(bus)\n",
    "                    for s in routes[bus]:\n",
    "                        if s not in visited_stop:\n",
    "                            # visited_stop.add(s)\n",
    "                            q.append((s, cost + 1))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:\n",
    "        g = defaultdict(list) # stop: [bus]\n",
    "        for bus, route in enumerate(routes):\n",
    "            for stop in route:\n",
    "                g[stop].append(bus)\n",
    "        \n",
    "        q = deque([(source, 0)])\n",
    "        buses = [set(r) for r in routes]\n",
    "        visited_bus, visited_stop = set(), set([source])\n",
    "        while q:\n",
    "            stop, cost = q.popleft()\n",
    "            if stop == target:\n",
    "                return cost\n",
    "            for bus in g[stop]:\n",
    "                if bus not in visited_bus:\n",
    "                    visited_bus.add(bus)\n",
    "                    for s in routes[bus]:\n",
    "                        if s not in visited_stop:\n",
    "                            visited_stop.add(s)\n",
    "                            q.append((s, cost + 1))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import deque\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:\n",
    "        \"\"\"\n",
    "        routes = [[1,2,7],[3,6,7]], source = 1, target = 6\n",
    "        :param routes:\n",
    "        :param source:\n",
    "        :param target:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        cnt = 0\n",
    "        if source == target:\n",
    "            return 0\n",
    "        m1 = {}\n",
    "        m2 = {}\n",
    "        for k, v in enumerate(routes):\n",
    "            m2[k] = set(v)\n",
    "            for i in v:\n",
    "                if i not in m1:\n",
    "                    m1[i] = [k]\n",
    "                else:\n",
    "                    m1[i].append(k)\n",
    "        dq = deque()\n",
    "        for i in m1[source]:\n",
    "            dq.append((i, 0))\n",
    "        used = {}\n",
    "        while len(dq) > 0:\n",
    "            first, step = dq.popleft()\n",
    "            if target in m2[first]:\n",
    "                return step + 1\n",
    "            if first not in used:\n",
    "                used[first] = step\n",
    "            else:\n",
    "                if step >= used[first]:\n",
    "                    continue\n",
    "            used[first] = step\n",
    "            for i in routes[first]:\n",
    "                for j in m1[i]:\n",
    "                    dq.append((j, step + 1))\n",
    "\n",
    "        return -1\n",
    "\n",
    "\n",
    "a = Solution()\n",
    "print(a.numBusesToDestination(routes=[[1, 2, 7], [3, 6, 7]], source=1, target=6))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:\n",
    "        if not routes:\n",
    "            return -1\n",
    "        if source == target:\n",
    "            return 0\n",
    "        q = collections.deque()\n",
    "        visited = set()\n",
    "        stops = collections.defaultdict(list)\n",
    "        for i, stop in enumerate(routes):\n",
    "            for point in stop:\n",
    "                stops[point].append(i)  \n",
    "        for busroute in stops[target]:\n",
    "            q.append((target, busroute, 1))\n",
    "            visited.add((target, busroute))\n",
    "        \n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                cur, route, bus = q.popleft()\n",
    "                if cur == source:\n",
    "                    return bus \n",
    "                for nex in routes[route]:\n",
    "                    if (nex, route) not in visited:\n",
    "                        q.append((nex, route, bus))\n",
    "                        visited.add((nex, route))\n",
    "                for newroute in stops[cur]:\n",
    "                    if (cur, newroute) not in visited:\n",
    "                        q.append((cur, newroute, bus + 1))\n",
    "                        visited.add((cur, newroute)) \n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:\n",
    "        g = collections.defaultdict(list)\n",
    "        visd = collections.defaultdict(int)\n",
    "        for r in range(len(routes)):\n",
    "            for st in routes[r]:\n",
    "                g[-r-1].append(st)\n",
    "                g[st].append(-r-1)\n",
    "        q = collections.deque()\n",
    "        q.append((source,0))\n",
    "        visd[source]=1\n",
    "        # print(g[100],g[285])\n",
    "        while q:\n",
    "            st,dis = q.popleft()     \n",
    "            if st == target:\n",
    "                return dis//2\n",
    "            for des in g[st]:\n",
    "                if des not in visd:\n",
    "                    visd[des]=1\n",
    "                    q.append((des,dis+1))\n",
    "        return -1\n",
    "                \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:\n",
    "        s2r = {}\n",
    "        for i in range(len(routes)):\n",
    "            for s in routes[i]:\n",
    "                if s not in s2r:\n",
    "                    s2r[s] = set()\n",
    "                s2r[s].add(i)\n",
    "        \n",
    "        if source == target:\n",
    "            return 0\n",
    "        if source not in s2r or target not in s2r:\n",
    "            return -1\n",
    "\n",
    "        q = [source]\n",
    "        steps = 1\n",
    "        visited = set()\n",
    "        while q:\n",
    "            next_q = []\n",
    "            for s in q:\n",
    "                for r in s2r[s]:\n",
    "                    if r in visited:\n",
    "                        continue\n",
    "                    visited.add(r)\n",
    "                    for t in routes[r]:\n",
    "                        if t == target:\n",
    "                            return steps\n",
    "                        next_q.append(t)\n",
    "            steps += 1\n",
    "            q = next_q\n",
    "\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:\n",
    "        edge = defaultdict(lambda: set())\n",
    "        stations = defaultdict(lambda: set())\n",
    "        n = len(routes)\n",
    "        for idx, r in enumerate(routes):\n",
    "            k = len(r)\n",
    "            for i in range(k):\n",
    "                for e in stations[r[i]]:\n",
    "                    edge[idx].add(e)\n",
    "                    edge[e].add(idx)\n",
    "                stations[r[i]].add(idx)\n",
    "                # for j in range(i+1, k):\n",
    "                #     edge[r[i]].add(r[j])\n",
    "                #     edge[r[j]].add(r[i])\n",
    "        \n",
    "        if target == source:\n",
    "            return 0\n",
    "        pq = deque([(1, idx) for idx in range(n) if idx in stations[source]])\n",
    "        ret = defaultdict(lambda: float('inf'))\n",
    "        while pq:\n",
    "            cost, cur = pq.popleft()\n",
    "            ret[cur] = cost\n",
    "            if cur in stations[target]:\n",
    "                return cost\n",
    "            for e in edge[cur]:\n",
    "                new_cost = cost+1\n",
    "                if ret[e] > new_cost:\n",
    "                    pq.append((new_cost, e))\n",
    "        #     print(pq)\n",
    "        # print(ret)\n",
    "        # print(edge)\n",
    "        return -1\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... \n",
    "        \n",
    "        if source == target:\n",
    "            return 0\n",
    "        start, end = set(), set()\n",
    "        s2r = collections.defaultdict(set)\n",
    "        for r, stations in enumerate(routes):\n",
    "            for s in stations:\n",
    "                if s == source:\n",
    "                    start.add(r)\n",
    "                elif s == target:\n",
    "                    end.add(r)\n",
    "                s2r[s].add(r)\n",
    "        if start & end:\n",
    "            return 1\n",
    "        conn = collections.defaultdict(set)\n",
    "        # for s in s2r:\n",
    "        #     for u in s2r[s]:\n",
    "        #         for v in s2r[s]:\n",
    "        #             if u != v:\n",
    "        #                 conn[u].add(v)\n",
    "        #                 conn[v].add(u)\n",
    "        for u in range(len(routes)):\n",
    "            for v in range(len(routes)):\n",
    "                if u != v and set(routes[u]) & set(routes[v]):\n",
    "                    conn[u].add(v)\n",
    "                    conn[v].add(u)\n",
    "        level = start.copy()\n",
    "        visit = start.copy()\n",
    "        count = 1\n",
    "        while level:\n",
    "            nextlevel = set()\n",
    "            count += 1\n",
    "            for u in level:\n",
    "                for v in conn[u]:\n",
    "                    if v in end:\n",
    "                        return count\n",
    "                    if v not in visit:\n",
    "                        nextlevel.add(v)\n",
    "                        visit.add(v)\n",
    "            level = nextlevel\n",
    "        return -1\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:\n",
    "        if target == source:\n",
    "            return 0\n",
    "        buses = collections.defaultdict(set)\n",
    "        l = len(routes)\n",
    "\n",
    "        through = collections.defaultdict(set)\n",
    "        for i in range(l):\n",
    "            for j in routes[i]:\n",
    "                through[j].add(i)\n",
    "        # print(through)\n",
    "\n",
    "        for i in through:\n",
    "            if len(through[i]) > 1:\n",
    "                for j in through[i]:\n",
    "                    if not buses[j]:\n",
    "                        buses[j] = through[i].copy()\n",
    "                    else:\n",
    "                        buses[j] = through[i].copy() | buses[j]\n",
    "        \n",
    "\n",
    "        for i in buses:\n",
    "            buses[i].remove(i)\n",
    "        print(buses)\n",
    "\n",
    "\n",
    "        start = set()\n",
    "        end = set()\n",
    "        for i in range(l):\n",
    "            if source in routes[i]:\n",
    "                start.add(i)\n",
    "        for i in range(l):\n",
    "            if target in routes[i]:\n",
    "                end.add(i)\n",
    "        print(start)\n",
    "        print(end)\n",
    "\n",
    "        path_l = []\n",
    "        \n",
    "        def bfs(s):\n",
    "            nonlocal buses, end, l\n",
    "            que = deque([s])\n",
    "            length = [1]\n",
    "            path = set()\n",
    "            path.add(s)\n",
    "            while que:\n",
    "                cur = que.popleft()\n",
    "                if cur in end:\n",
    "                    return length[0]\n",
    "                for j in buses[cur] - path:\n",
    "                    que.append(j)\n",
    "                    length.append(length[0]+1)\n",
    "                    path.add(j)\n",
    "                length.pop(0)\n",
    "\n",
    "\n",
    "        for i in start:\n",
    "            a = bfs(i) # 这里要注意，当不联通的时候，bsf(i)返回None\n",
    "            if a:\n",
    "                path_l.append(a) \n",
    "        \n",
    "        print(path_l)\n",
    "\n",
    "        if path_l:\n",
    "            return min(path_l)\n",
    "        else:\n",
    "            return -1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:\n",
    "        if target == source:\n",
    "            return 0\n",
    "        buses = collections.defaultdict(set)\n",
    "        l = len(routes)\n",
    "\n",
    "        through = collections.defaultdict(set)\n",
    "        for i in range(l):\n",
    "            for j in routes[i]:\n",
    "                through[j].add(i)\n",
    "        # print(through)\n",
    "\n",
    "        for i in through:\n",
    "            if len(through[i]) > 1:\n",
    "                for j in through[i]:\n",
    "                    if not buses[j]:\n",
    "                        buses[j] = through[i].copy()\n",
    "                    else:\n",
    "                        buses[j] = through[i].copy() | buses[j]\n",
    "        \n",
    "\n",
    "        for i in buses:\n",
    "            buses[i].remove(i)\n",
    "        print(buses)\n",
    "\n",
    "\n",
    "        start = set()\n",
    "        end = set()\n",
    "        for i in range(l):\n",
    "            if source in routes[i]:\n",
    "                start.add(i)\n",
    "        for i in range(l):\n",
    "            if target in routes[i]:\n",
    "                end.add(i)\n",
    "        print(start)\n",
    "        print(end)\n",
    "\n",
    "        path_l = []\n",
    "        \n",
    "        def bfs(s):\n",
    "            nonlocal buses, end, l\n",
    "            que = deque([s])\n",
    "            length = [1]\n",
    "            path = set()\n",
    "            path.add(s)\n",
    "            while que:\n",
    "                cur = que.popleft()\n",
    "                if cur in end:\n",
    "                    return length[0]\n",
    "                for j in buses[cur]:\n",
    "                    if j not in path:\n",
    "                        que.append(j)\n",
    "                        length.append(length[0]+1)\n",
    "                        path.add(j)\n",
    "                length.pop(0)\n",
    "\n",
    "\n",
    "        for i in start:\n",
    "            a = bfs(i) # 这里要注意，当不联通的时候，bsf(i)返回None\n",
    "            if a:\n",
    "                path_l.append(a) \n",
    "        \n",
    "        print(path_l)\n",
    "\n",
    "        if path_l:\n",
    "            return min(path_l)\n",
    "        else:\n",
    "            return -1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict, deque\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:\n",
    "        if source == target:\n",
    "            return 0\n",
    "\n",
    "        # 构建站点到公交线路的映射\n",
    "        stop_to_routes = defaultdict(set)\n",
    "        for i, route in enumerate(routes):\n",
    "            for stop in route:\n",
    "                stop_to_routes[stop].add(i)\n",
    "\n",
    "        # 初始化 BFS 队列和访问集合\n",
    "        queue = deque([source])\n",
    "        visited_routes = set()\n",
    "        visited_stops = set([source])\n",
    "\n",
    "        # BFS 进行搜索\n",
    "        transfers = 0\n",
    "        while queue:\n",
    "            size = len(queue)\n",
    "            for _ in range(size):\n",
    "                current_stop = queue.popleft()\n",
    "\n",
    "                # 获取当前站点可以搭乘的公交线路\n",
    "                current_routes = stop_to_routes[current_stop]\n",
    "\n",
    "                # 遍历所有可能的下一站\n",
    "                for route_idx in current_routes:\n",
    "                    if route_idx not in visited_routes:\n",
    "                        visited_routes.add(route_idx)\n",
    "                        for next_stop in routes[route_idx]:\n",
    "                            if next_stop == target:\n",
    "                                return transfers + 1\n",
    "                            if next_stop not in visited_stops:\n",
    "                                visited_stops.add(next_stop)\n",
    "                                queue.append(next_stop)\n",
    "\n",
    "            transfers += 1\n",
    "\n",
    "        return -1  # 如果无法到达目标站点，则返回 -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:\n",
    "        if source == target:\n",
    "            return 0\n",
    "        graph = defaultdict(set)\n",
    "        for bus_num, stops in enumerate(routes):\n",
    "            for stop in stops:\n",
    "                graph[stop].add(bus_num)\n",
    "            \n",
    "        visited_stops = set()\n",
    "        visited_buses = set()\n",
    "        deq = deque([(source, 0)])\n",
    "        while deq:\n",
    "            stop, cnt = deq.popleft()\n",
    "            if stop == target:\n",
    "                return cnt\n",
    "            for bus_num in graph[stop]:\n",
    "                if bus_num not in visited_buses:\n",
    "                    visited_buses.add(bus_num)\n",
    "                    for stop in routes[bus_num]:\n",
    "                        if stop not in visited_stops:\n",
    "                            visited_stops.add(stop)\n",
    "                            deq.append((stop, cnt+1))\n",
    "        \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:\n",
    "        if source == target: return 0\n",
    "        d, used_line, used_station = {}, set(), set()\n",
    "        for cnt, route in enumerate(routes):\n",
    "            for r in route:\n",
    "                if r not in d: d[r] = set()\n",
    "                d[r].add(cnt)\n",
    "        used_line = d[source]\n",
    "        used_station = set(sum([routes[i] for i in d[source]], []))\n",
    "        l = [set(used_station)]\n",
    "        while l[-1]: \n",
    "            s = set()\n",
    "            for station in l[-1]:\n",
    "                if station==target: return len(l)\n",
    "                for line_index in d[station]:\n",
    "                    if line_index not in used_line:\n",
    "                        used_line.add(line_index)\n",
    "                        for next_station in routes[line_index]:\n",
    "                            if next_station not in used_station:\n",
    "                                s.add(next_station)\n",
    "                                used_station.add(next_station)\n",
    "            l.append(s)\n",
    "        return -1             "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:\n",
    "        g = defaultdict(list)\n",
    "        station = defaultdict(list)\n",
    "        for i, route in enumerate(routes):\n",
    "            for a, b in pairwise(route + [route[0]]):\n",
    "                g[a].append(b)\n",
    "                station[a].append(i)\n",
    "\n",
    "        dq = deque([source])\n",
    "        v = set([source])\n",
    "        v_r = set()\n",
    "        bus = 0\n",
    "        while dq:\n",
    "            size = len(dq)\n",
    "            while size:\n",
    "                o = dq.popleft()\n",
    "                if o == target:\n",
    "                    return bus\n",
    "                for i in station[o]:\n",
    "                    if i in v_r:\n",
    "                        continue\n",
    "                    v_r.add(i)\n",
    "                    for p in routes[i]:\n",
    "                        if p in v:\n",
    "                            continue\n",
    "                        dq.append(p)\n",
    "                        v.add(p)\n",
    "                size -= 1\n",
    "            bus += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:\n",
    "        # 每个车站可以乘坐的公交车\n",
    "        stations = defaultdict(set)\n",
    "        for i, stops in enumerate(routes):\n",
    "            for stop in stops:\n",
    "                stations[stop].add(i)\n",
    "        # 每个公交车线路可以到达的车站\n",
    "        routes = [set(x) for x in routes]\n",
    "\n",
    "        q = deque([(source, 0)])\n",
    "        # 已经乘坐了的公交车\n",
    "        buses = set()\n",
    "        # 已经到达了的车站\n",
    "        stops = {source}\n",
    "        while q:\n",
    "            pos, cost = q.popleft()\n",
    "            if pos == target:\n",
    "                return cost\n",
    "            # 当前车站中尚未乘坐的公交车\n",
    "            for bus in stations[pos] - buses:\n",
    "                # 该公交车尚未到达过的车站\n",
    "                for stop in routes[bus] - stops:\n",
    "                    buses.add(bus)\n",
    "                    stops.add(stop)\n",
    "                    q.append((stop, cost + 1))\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:\n",
    "        stations = collections.defaultdict(set)\n",
    "        for i, route in enumerate(routes):\n",
    "            for station in route:\n",
    "                stations[station].add(i)\n",
    "        \n",
    "        routes = [set(x) for x in routes]\n",
    "        q = deque()\n",
    "        q.append((source,0))\n",
    "        buses = set()\n",
    "        stops = {source} # set 直接这么建立\n",
    "        # set - set 操作\n",
    "        # 重复的bus 和 stop 没用\n",
    "\n",
    "        while q :\n",
    "            stop, cost = q.popleft()\n",
    "            if stop == target:\n",
    "                return cost\n",
    "            \n",
    "            for bus in stations[stop] - buses:\n",
    "                for stop in routes[bus] - stops:\n",
    "                    buses.add(bus)\n",
    "                    stops.add(stop)\n",
    "                    q.append((stop, cost + 1))\n",
    "        \n",
    "        return -1\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:\n",
    "        l = len(routes)\n",
    "        stations = defaultdict(set)\n",
    "        for bus in range(l):\n",
    "            for stop in routes[bus]:\n",
    "                stations[stop].add(bus)\n",
    "        print(stations)\n",
    "\n",
    "        bus_routes = defaultdict(set)\n",
    "        for bus, route in enumerate(routes):\n",
    "            bus_routes[bus] = set(route)\n",
    "\n",
    "        print(bus_routes)\n",
    "\n",
    "        que = deque([(source, 0)]) # 使用deque可以大幅加快速度\n",
    "        taken_buses = set()\n",
    "        visited_stops = set()\n",
    "        visited_stops.add(source)\n",
    "        while que:\n",
    "            cur_stop, num_buses = que.popleft()\n",
    "            # 检查是否到站：\n",
    "            if cur_stop == target:\n",
    "                return num_buses\n",
    "            # 当下车站可以坐的车：\n",
    "            for bus in stations[cur_stop] - taken_buses: \n",
    "                    # 这个车可以到达的车站\n",
    "                    for stop in bus_routes[bus] - visited_stops:\n",
    "                        taken_buses.add(bus)\n",
    "                        visited_stops.add(stop)\n",
    "                        que.append((stop, num_buses+1))\n",
    "        \n",
    "        return -1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:\n",
    "        if source==target:\n",
    "            return 0\n",
    "        n=len(routes)\n",
    "        adlist=defaultdict(set)\n",
    "        visited_station=set()\n",
    "        visited_route=set()\n",
    "        for i,route in enumerate(routes):\n",
    "            for x in route:\n",
    "                adlist[(x,0)].add(i)\n",
    "                adlist[(i,1)].add(x)\n",
    "        Q=deque([source])\n",
    "        deep=0\n",
    "        while Q:\n",
    "            #先站点\n",
    "            for _ in range(len(Q)): \n",
    "                x=Q.popleft()\n",
    "                for y in adlist[(x,0)]:\n",
    "                    if y not in visited_route:\n",
    "                        visited_route.add(y)\n",
    "                        Q.append(y)\n",
    "            deep+=1\n",
    "            #后线路点\n",
    "            for _ in range(len(Q)):\n",
    "                x=Q.popleft()\n",
    "                if target in adlist[(x,1)]:\n",
    "                    return deep\n",
    "                for y in adlist[(x,1)]:\n",
    "                    if y not in visited_station:\n",
    "                        visited_station.add(y)\n",
    "                        Q.append(y)\n",
    "        return -1\n",
    "\n",
    "\n",
    "'''\n",
    "法一 建图+bfs\n",
    "图中分两类节点，一类是站点，一类是线路点\n",
    "站点只直连线路点，线路点只直连站点\n",
    "\n",
    "一个站点和与其途经的线路有边\n",
    "\n",
    "只要从源站bfs到达终点站即可\n",
    "时间复杂度O(sum(routes[i].length))\n",
    "空间复杂度O(n+m)\n",
    "\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:\n",
    "        graph = defaultdict(set)\n",
    "        for bus, stops in enumerate(routes):\n",
    "            for stop in stops:\n",
    "                graph[-bus-1].add(stop)\n",
    "                graph[stop].add(-bus-1)\n",
    "        print(graph)\n",
    "        visited = {source}\n",
    "        que = deque([source])\n",
    "        times = 0\n",
    "        while que:\n",
    "            for _ in range(len(que)):\n",
    "                cur = que.popleft()\n",
    "                if cur == target:\n",
    "                    return times // 2\n",
    "                for nei in graph[cur]:\n",
    "                    if nei not in visited:\n",
    "                        que.append(nei)\n",
    "                        visited.add(nei)\n",
    "            times += 1\n",
    "        return -1\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
